package kyssion.leetcode.num201_250;

import kyssion.leetcode.util.ShowUtil;

public class code204_计数质数 {

    public static void main(String[] args) {
        int[] item = new code204_计数质数().prime(2);
        ShowUtil.showArr(item);
        System.out.println(new code204_计数质数().countPrimes(2));
    }

    /**
     * 快速筛法求素数
     *
     * @param MAX
     * @return
     */

    public int countPrimes(int MAX) {
        int cnt = 1;
        int[] su = new int[MAX + 1];
        //false 是素数
        boolean[] isprime = new boolean[MAX + 1];//初始化认为所有数都为素数
        isprime[0] = isprime[1] = true;//0和1不是素数
        for (int i = 2; i < MAX; i++) {
            if (!isprime[i])
                su[cnt++] = i;//保存素数i
            for (int j = 1; j < cnt && su[j] * i < MAX; j++) {
                isprime[su[j] * i] = true;//筛掉小于等于i的素数和i的积构成的合数
            }
        }
        return cnt-1;
    }


    int[] prime(int MAX) {
        int cnt = 1;
        int[] su = new int[MAX + 1];
        //false 是素数
        boolean[] isprime = new boolean[MAX + 1];//初始化认为所有数都为素数
        isprime[0] = isprime[1] = true;//0和1不是素数
        for (int i = 2; i <= MAX; i++) {
            if (!isprime[i])
                su[cnt++] = i;//保存素数i
            for (int j = 1; j <= cnt && su[j] * i <= MAX; j++) {
                isprime[su[j] * i] = true;//筛掉小于等于i的素数和i的积构成的合数
            }
        }
        return su;
    }
}
